package com.example.temp;


public class Test22 {

    public static void main(String[] args) {

    }

    /**
     * 输入一个非空整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
     * 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同
     */
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }
    }
    /**
     * 二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，
     * 或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
     * 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
     * 二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势
     */

    public class Solution {

        public boolean VerifySquenceOfBST(int [] sequence) {
            if (sequence.length==0)return false;
            if (sequence.length==1)return true;

            return solve(sequence,0,sequence.length-1);

        }

        private boolean solve(int[] a,int satrt, int root) {

            //说明i经遍历到头没有发现返回false的情况
            if (satrt>=root)return true;
//            找到根节点
            int i = root;
//            找到左右子树分界点 从起始i-1开始寻找 i-- 直到找到
            while (i>satrt&&a[i-1]>a[root])i--;

            for (int j = satrt; j < i-1; j++) {
                if (a[j]>a[root])
                    return false;
            }
            return solve(a,satrt,i-1)&&solve(a,i,root-1);
        }
    }
}
